33. 搜索旋转排序数组

Similar Question

Solution Tips

方案一: 二分搜索

题目

• 假设按照升序排序的数组在预先未知的某个点上进行了旋转。

  ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

• 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

• 你可以假设数组中不存在重复的元素。

• 你的算法时间复杂度必须是 O(log n) 级别。

  输入: nums = [4,5,6,7,0,1,2], target = 0
  输出: 4
  
  输入: nums = [4,5,6,7,0,1,2], target = 3
  输出: -1
  

分析

• 有点像二分搜索
• 先进行一次二分搜索找到旋转点，然后判断应该在左半边还是右半边，再进行一次二分查找

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int idx = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                idx = i;
                break;
            }
        }
        int ans = find(nums, 0, idx, target);
        if (ans != -1) return ans;
        if (idx + 1 < n) ans = find(nums, idx + 1, n - 1, target);
        return ans;
    }
    int find(int[] nums, int l, int r, int target) {
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
}